package DP;

import java.util.*;
/**
 * @author 曹见朋
 * @create 2024-06-13-19:52
 */
public class Main139 {
    // TODO 139. 单词拆分
    public static boolean wordBreak(String s, List<String> wordDict) {

        HashSet<String> set = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i && !dp[i]; j++){
                if(set.contains(s.substring(j, i)) && dp[j]){
                    dp[i] = true;
                }

            }
        }

        return dp[n];
    }

    public static void main(String[] args){
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        boolean b = wordBreak(s, wordDict);
        System.out.println(b);

    }
}
